#include "spfa.h"
#include <queue>
#include <vector>
#include <functional>

// SPFA算法实现，用于求解单源最短路径
SPFAResult spfa(const QVector<QVector<double>> &graph, int startNode) {
    int n = graph.size();  // 图中节点数量
    SPFAResult result;
    result.distances = QVector<double>(n, std::numeric_limits<double>::infinity()); // 初始化距离向量为正无穷
    result.predecessors = QVector<int>(n, -1);  // 初始化前驱节点向量为-1

    result.distances[startNode] = 0;  // 起点到自身的距离为0

    // 使用优先队列（最小堆），存储(当前最短距离, 节点)
    std::priority_queue<std::pair<double, int>, std::vector<std::pair<double, int>>, std::greater<>> pq;
    pq.push({0, startNode});  // 将起点加入优先队列，初始距离为0

    // 主循环：遍历队列中的节点，更新最短路径
    while (!pq.empty()) {
        int u = pq.top().second;  // 取出队列顶端节点（当前距离最小的节点）
        double uDist = pq.top().first;  // 取出该节点的最小距离
        pq.pop();  // 弹出队列顶端元素

        // 如果当前路径的距离大于已知最短距离，则跳过该路径
        if (uDist > result.distances[u]) continue;

        // 遍历节点u的所有邻接节点v，尝试更新v的最短距离
        for (int v = 0; v < n; ++v) {
            // 如果从u到v存在边且通过u到v的路径更短，则更新v的距离和前驱
            if (graph[u][v] != std::numeric_limits<double>::infinity() && result.distances[u] + graph[u][v] < result.distances[v]) {
                result.distances[v] = result.distances[u] + graph[u][v];  // 更新v的最短距离
                result.predecessors[v] = u;  // 更新v的前驱节点为u
                pq.push({result.distances[v], v});  // 将v和其更新后的距离加入优先队列
            }
        }
    }

    return result;  // 返回计算结果，包括各节点的最短距离和前驱节点信息
}

// 根据前驱节点数组重建从起点到终点的路径
QVector<int> getPath(const QVector<int> &predecessors, int startNode, int endNode) {
    QVector<int> pathNodes;

    // 从终点逆向追踪路径，直到起点
    for (int at = endNode; at != -1; at = predecessors[at]) {
        pathNodes.push_back(at);
    }
    std::reverse(pathNodes.begin(), pathNodes.end());  // 反转路径，使其从起点到终点

    // 检查路径的起点是否为startNode
    if (!pathNodes.isEmpty() && pathNodes.front() != startNode) {
        pathNodes.clear();  // 如果路径不正确，则返回空路径
    }

    return pathNodes;  // 返回路径（若存在）
}
